#include "terrianGLSL.h"
#include "GL/glut.h"

#include <cmath>
#include <iostream>
#include <strstream>
#include <algorithm>
#include <set>
#include <stack>

#include "demDataLoad.h"

#include <time.h>

using namespace std;

int * temDemDatap = NULL;

void detailTerrainGridCreate()
{
	AppGloble::terrainDetailCallListNum = glGenLists(1);

	glNewList(AppGloble::terrainDetailCallListNum, GL_COMPILE);
	
	for(int row=0; row<AppGloble::detailGridNum; ++row)
	{
		glBegin(GL_TRIANGLE_STRIP);
		
		for(int col=1; col<=AppGloble::detailGridNum; ++col)
		{			
			glVertex3f(col/float(AppGloble::detailGridNum)-0.5f, row/float(AppGloble::detailGridNum)-0.5f,		0.0f);		
			glVertex3f(col/float(AppGloble::detailGridNum)-0.5f, (row+1)/float(AppGloble::detailGridNum)-0.5f,	0.0f);					
		}		
		glEnd();
	}
	glEndList();
}

void moreDetailTerrainGridCreate()
{
	AppGloble::terrainMoreDetailCallListNum = glGenLists(1);

	glNewList(AppGloble::terrainMoreDetailCallListNum, GL_COMPILE);

	for(int row=0; row<AppGloble::detailGridNum; ++row)
	{
		glBegin(GL_TRIANGLE_STRIP);

		for(int col=0; col<=AppGloble::detailGridNum; ++col)
		{			
			glVertex3f((col/float(AppGloble::detailGridNum)-0.5f)/2.0f, 
					   (row/float(AppGloble::detailGridNum)-0.5f)/2.0f,
					   0.0f);		
			glVertex3f((col/float(AppGloble::detailGridNum)-0.5f)/2.0f, 
					   ((row+1)/float(AppGloble::detailGridNum)-0.5f)/2.0f,	
					   0.0f);					
		}		
		glEnd();
	}

	for(int row=0; row<AppGloble::detailGridNum; ++row)
	{
		
		if(row<(AppGloble::detailGridNum/4) || row>(3*AppGloble::detailGridNum/4))
		{
			glBegin(GL_TRIANGLE_STRIP);
			for(int col=0; col<=AppGloble::detailGridNum; ++col)
			{			

				glVertex3f(col/float(AppGloble::detailGridNum)-0.5f, 
							row/float(AppGloble::detailGridNum)-0.5f,
							0.0f);		
				glVertex3f(col/float(AppGloble::detailGridNum)-0.5f, 
							(row+1)/float(AppGloble::detailGridNum)-0.5f,	
							0.0f);					
			}	
			glEnd();
		}			
		else
		{
			glBegin(GL_TRIANGLE_STRIP);
			for(int col=0; col<=AppGloble::detailGridNum/4; ++col)
			{			

				glVertex3f(col/float(AppGloble::detailGridNum)-0.5f, 
					row/float(AppGloble::detailGridNum)-0.5f,
					0.0f);		
				glVertex3f(col/float(AppGloble::detailGridNum)-0.5f, 
					(row+1)/float(AppGloble::detailGridNum)-0.5f,	
					0.0f);					
			}	
			glEnd();

			glBegin(GL_TRIANGLE_STRIP);
			for(int col=3*AppGloble::detailGridNum/4; col<=AppGloble::detailGridNum; ++col)
			{			

				glVertex3f(col/float(AppGloble::detailGridNum)-0.5f, 
					row/float(AppGloble::detailGridNum)-0.5f,
					0.0f);		
				glVertex3f(col/float(AppGloble::detailGridNum)-0.5f, 
					(row+1)/float(AppGloble::detailGridNum)-0.5f,	
					0.0f);					
			}	
			glEnd();
		}
		
	}

	glEndList();
}

void terrianGridCreate_()
{
	AppGloble::terrainCallListNum = glGenLists(1);

	glNewList(AppGloble::terrainCallListNum, GL_COMPILE);

	if(AppGloble::usingGLSL20)
	{
		glBegin(GL_TRIANGLES);
		for(float row=0.0f; row<3.0f; row+=0.003f)
		{
			//glBegin(GL_TRIANGLE_STRIP);		
			for(float col=0.0f; col<3.0f; col+=0.003f)
			{
				//glTexCoord2f(row/3.0f, col/3.0f);
				glVertex3f(row, col, 1.0f);
				//glTexCoord2f((row+0.003f)/3.0f, col/3.0f);
				//glVertex3f(row+0.003f, col, 1.0f);
			}		
			//glEnd();
		}
		glEnd();
	}
	else
	{
		glColor3f(0.2,.06,.03);
		glutSolidTeapot(1.0);	
	}

	glEndList();	
}

void terrianGridCreate_fix_()
{
	if(temDemDatap==NULL)
		return;

	AppGloble::terrainCallListNum = glGenLists(1);

	glNewList(AppGloble::terrainCallListNum, GL_COMPILE);

	for(int row=0; row<1023; ++row)
	{
		glBegin(GL_TRIANGLE_STRIP);
		for(int col=0; col<1024; ++col)
		{
			//glTexCoord2f(row/3.0f, col/3.0f);
			glVertex3f(float(row)/333.0, float(col)/333.0, temDemDatap[row*2*2048+col*2]/9000.0);
			//glTexCoord2f((row+0.003f)/3.0f, col/3.0f);
			glVertex3f(float(row+1)/333.0, float(col)/333.0, temDemDatap[(row+1)*2*2048+col*2]/9000.0);
		}
		glEnd();
	}

	glEndList();
}

bool radomSort(const gpoint * const pre, const gpoint * const sub)
{
	return (1 == (rand()%2));
}

bool nonUniformTerrainGridCreate(unsigned char* dataBlob, 
								 const int lenx, 
								 const int leny, 
								 const float renderSizex,
								 const float renderSizey,
								 const float roughDegree)
{
	cout<<endl<<"in function nonUniformTerrainGridCreate"<<endl;

	if(dataBlob==NULL)
		return false;

	//to store all the point data into array of gpoint objec
	float *theData = (float*)dataBlob;
	gpoint *theGridPoints  = new gpoint[lenx*leny];

	long tcount = 0;
	float rx, ry;

	cout<<endl<<"to generate the array of the gpoint object";
	for(int row=0; row<leny; ++row)
	{		
		if(row%(100)==0)
		{
			cout<<endl<<"array generate -- "<<100.0f*(float(row)/float(leny))<<" %";
		}

		ry = float(row)/float(leny);
		for(int col=0; col<lenx; ++col)
		{
			rx = float(col)/float(lenx);

			theGridPoints[tcount].cx = rx*renderSizex;
			theGridPoints[tcount].cy = ry*renderSizey;
			theGridPoints[tcount].hv = theData[row*lenx+col];
			++tcount;
		}
	}

	cout<<endl<<"to compute the rough degree";

	int tmprow, tmpcol, tmphv;

	//to compute the roughdegree for every point
	std::vector<const gpoint* > roughGridPoints;	

	for(int row=0; row<leny; ++row)
	{			
		if(row%(100)==0)
		{
			cout<<endl<<"roughdegree compute -- "<<100.0f*(float(row)/float(leny))<<" %";
		}

		for(int col=0; col<lenx; ++col)
		{
			theGridPoints[row*lenx+col].qfv = 0;

			tmpcol = col-1;
			tmprow = row-1;
			if(tmpcol<0 || tmpcol>=lenx || tmprow<0 || tmprow>=leny)
				tmphv = 0.0f;
			else
				tmphv = theGridPoints[tmprow*lenx+tmpcol].hv;

			theGridPoints[row*lenx+col].qfv += abs(theGridPoints[row*lenx+col].hv - tmphv);

			tmpcol = col;
			tmprow = row-1;
			if(tmpcol<0 || tmpcol>=lenx || tmprow<0 || tmprow>=leny)
				tmphv = 0.0f;
			else
				tmphv = theGridPoints[tmprow*lenx+tmpcol].hv;

			theGridPoints[row*lenx+col].qfv += abs(theGridPoints[row*lenx+col].hv - tmphv);

			tmpcol = col+1;
			tmprow = row;
			if(tmpcol<0 || tmpcol>=lenx || tmprow<0 || tmprow>=leny)
				tmphv = 0.0f;
			else
				tmphv = theGridPoints[tmprow*lenx+tmpcol].hv;

			theGridPoints[row*lenx+col].qfv += abs(theGridPoints[row*lenx+col].hv - tmphv);

			tmpcol = col;
			tmprow = row+1;
			if(tmpcol<0 || tmpcol>=lenx || tmprow<0 || tmprow>=leny)
				tmphv = 0.0f;
			else
				tmphv = theGridPoints[tmprow*lenx+tmpcol].hv;

			theGridPoints[row*lenx+col].qfv += abs(theGridPoints[row*lenx+col].hv - tmphv);			

			if(theGridPoints[row*lenx+col].qfv < roughDegree)
				roughGridPoints.push_back(&(theGridPoints[row*lenx+col]));
		}
	}	

	std::list<nutrian> untriangles;

	srand( (unsigned)time( NULL ) );
	std::sort(roughGridPoints.begin(), roughGridPoints.end(), radomSort);	

	//to do the delaunay process
	if(!doDelaunay(roughGridPoints, untriangles))
		return false;

	

	//to form the terrain grid using the result of delaunay process
	cout<<endl<<endl<<"to generate the grid call list";


	AppGloble::terrainCallListNum = glGenLists(1);

	glNewList(AppGloble::terrainCallListNum, GL_COMPILE);

	glBegin(GL_TRIANGLES);

	for(std::list<nutrian>::iterator traitr = untriangles.begin();
		traitr!= untriangles.end();
		++traitr)
	{
		glVertex3f((*traitr).getP1()->cx,(*traitr).getP1()->cy,(*traitr).getP1()->hv);
		glVertex3f((*traitr).getP2()->cx,(*traitr).getP2()->cy,(*traitr).getP2()->hv);
		glVertex3f((*traitr).getP3()->cx,(*traitr).getP3()->cy,(*traitr).getP3()->hv);
	}

	glEnd();

	glEndList();

	delete []theGridPoints;
	
	return true;
}

//======================================================================

gpoint nowDelaunayPoint;

float angleCompute(float tox, float toy, float fromx, float fromy)
{
	float angl;
	
	if(abs(tox - fromx)<1.0e-6)
	{
		angl = ((toy-fromy)>0.0f) ? (3.1416/2.0f) : (3.0f*3.1416/2.0f);

		return angl;
	}
	
	if(abs(toy - fromy)<1.0e-6)
	{
		angl = ((tox - fromx)>0.0f) ? 0.0f : 3.1416;

		return angl;
	}

	angl = acos((tox - fromx)/((tox-fromx)*(tox-fromx) + (toy-fromy)*(toy-fromy)));	

	angl = (toy-fromy)>0 ? angl : 2*3.1416-angl;

	return angl;
}

bool holePointsSortGreater(const gpoint * const pre, const gpoint * const sub) 
{
	return (angleCompute(pre->cx, pre->cy, nowDelaunayPoint.cx, nowDelaunayPoint.cy) > 
		    angleCompute(sub->cx, sub->cy, nowDelaunayPoint.cx, nowDelaunayPoint.cy));
}

bool doDelaunay(std::vector<const gpoint*> & thePointArray, std::list<nutrian> &untriangles)
{
	if(thePointArray.size()<3)
		return false;
	
	untriangles.clear();

	//find out the border of the point set
	float miny,maxy,minx,maxx;

	miny=maxy=minx=maxx=0.0f;

	for(std::vector<const gpoint* >::iterator itr = thePointArray.begin();
		itr != thePointArray.end();
		++itr)
	{
		minx = (*itr)->cx<minx ? (*itr)->cx : minx;
		maxx = (*itr)->cx>maxx ? (*itr)->cx : maxx;

		miny = (*itr)->cy<miny ? (*itr)->cy : miny;
		maxy = (*itr)->cy>maxy ? (*itr)->cy : maxy;
	}	

	minx -= 1.0;
	miny -= 1.0;

	maxx += 1.0;
	maxy += 1.0;

	//build a big triangle to contain all the points
	gpoint initP1;
	initP1.cx = minx;
	initP1.cy = miny;

	gpoint initP2;
	initP2.cx = minx;
	initP2.cy = 2.0f*maxy-miny;

	gpoint initP3;
	initP3.cx = 2.0f*maxx-minx;
	initP3.cy = miny;

	nutrian iniTrian(&initP1, &initP2, &initP3);
	
	untriangles.push_back(iniTrian);	

	std::set<const gpoint*> holePointsSet;		
	std::vector<const gpoint*> holePointsVec;		

	//begin the delaunay dissect
	for(unsigned int i=0; i<thePointArray.size(); ++i)
	{
		if(i%(1024)==0)
		{
			cout<<endl<<"delaunay implement -- "<<100.0f*(float(i)/float(thePointArray.size()))<<" %";
		}

		holePointsSet.clear();

		holePointsVec.clear();

		nowDelaunayPoint = *(thePointArray[i]);
		//nowDelaunayPoint = &tmp;

		std::set<const gpoint*> holePoints;		

		std::list<nutrian>::iterator todeleteItr = untriangles.end();
		//to find out all the triangles whose circle contain the point 
		
		//if(AppGloble::detailPrint)
		cout<<endl<<endl<<i<<" the triangle size"<<untriangles.size()<<"\t"
			<<"<"<<nowDelaunayPoint.cx<<",\t"<<nowDelaunayPoint.cy<<">";

		int tCount = 0;
		if(AppGloble::detailPrint)
		for(std::list<nutrian>::iterator traitr = untriangles.begin();
			traitr!= untriangles.end();
			++traitr)
		{
			tCount++;
			cout<<endl
				<<"t"<<tCount<<(long)((*traitr).getP1())
				<<"<"<<(*traitr).getP1()->cx<<",\t"<<(*traitr).getP1()->cy<<">\t"
				<<"<"<<(*traitr).getP2()->cx<<",\t"<<(*traitr).getP2()->cy<<">\t"
				<<"<"<<(*traitr).getP3()->cx<<",\t"<<(*traitr).getP3()->cy<<">";
		}

		int deleteCount = 0;
		for(std::list<nutrian>::iterator traitr = untriangles.begin();
			traitr!= untriangles.end();
			++traitr)
		{
			if(!(*traitr).isInCircle(nowDelaunayPoint))
				continue;

			//store all the points of the deleting triangles
			holePointsSet.insert((*traitr).getP1());
			holePointsSet.insert((*traitr).getP2());
			holePointsSet.insert((*traitr).getP3());

			//delete the triangles whose circle contain the point 
			if(todeleteItr!=untriangles.end())
			{
				untriangles.erase(todeleteItr);
				++deleteCount;
			}

			todeleteItr = traitr;
			
			//traitr = untriangles.begin();
		}	

		if(todeleteItr!=untriangles.end())
		{
			untriangles.erase(todeleteItr);
			++deleteCount;
		}

		if(AppGloble::detailPrint)
			cout<<endl<<i<<" the triangle size"<<untriangles.size()<<" deletecout "<<deleteCount
				<<" holePointsSet size "<<holePointsSet.size();

		//===================================sort all the points order by the angle 
		for(std::set<const gpoint*>::iterator pssItr = holePointsSet.begin();
			pssItr!= holePointsSet.end();
			++pssItr
			)
		{
			holePointsVec.push_back((*pssItr));
			if(AppGloble::detailPrint)
			cout<<endl<<"point of the hole "
				<<"<"<<(*pssItr)->cx<<",\t"<<(*pssItr)->cy<<">";
		}

		std::sort(holePointsVec.begin(), holePointsVec.end(), holePointsSortGreater);

		if(AppGloble::detailPrint)
			cout<<endl<<i<<" holePointsVec size"<<holePointsVec.size();

		//==================================generate new triangles
		for(std::vector<const gpoint*>::iterator pssItr = holePointsVec.begin();
			pssItr!= holePointsVec.end();
			++pssItr)
		{
			const gpoint* tmp1 = (*pssItr);
			++pssItr;

			if(pssItr != holePointsVec.end())
			{
				const gpoint*  tmp2 = (*pssItr);

				nutrian tmpTriagl(thePointArray[i], tmp1, tmp2);

				untriangles.push_back(tmpTriagl);	
			}
			else
			{
				const gpoint*  tmp2 = (*(holePointsVec.begin()));	

				nutrian tmpTriagl(thePointArray[i], tmp1, tmp2);

				untriangles.push_back(tmpTriagl);
			}		

			--pssItr;
		}

		tCount = 0;

		if(AppGloble::detailPrint)
		for(std::list<nutrian>::iterator traitr = untriangles.begin();
			traitr!= untriangles.end();
			++traitr)
		{
			tCount++;
			cout<<endl
				<<"bt"<<tCount<<(long)((*traitr).getP1())
				<<"<"<<(*traitr).getP1()->cx<<",\t"<<(*traitr).getP1()->cy<<">\t"
				<<"<"<<(*traitr).getP2()->cx<<",\t"<<(*traitr).getP2()->cy<<">\t"
				<<"<"<<(*traitr).getP3()->cx<<",\t"<<(*traitr).getP3()->cy<<">";
		}
	}

	cout<<endl<<"to delete the triangles with the initial triangl points";
	int deleteCount=0;
	std::list<nutrian>::iterator todeleteItr = untriangles.end();

	for(std::list<nutrian>::iterator traitr = untriangles.begin();
		traitr!= untriangles.end();
		++traitr)
	{
		if((*traitr).getP1() == &initP1 || (*traitr).getP1()==&initP2 || (*traitr).getP1()==&initP3 ||
		   (*traitr).getP2() == &initP1 || (*traitr).getP2()==&initP2 || (*traitr).getP2()==&initP3 ||
		   (*traitr).getP3() == &initP1 || (*traitr).getP3()==&initP2 || (*traitr).getP3()==&initP3)		
		{

		}
		else
		{
			continue;
		}

		if(todeleteItr!=untriangles.end())
		{
			untriangles.erase(todeleteItr);
			++deleteCount;
		}

		todeleteItr = traitr;
	}

	if(todeleteItr!=untriangles.end())
	{
		untriangles.erase(todeleteItr);
		++deleteCount;
	}


	return true;
}

//======================================================================

const float nonuniformTriangle::inDst = 1.0e-3;

nonuniformTriangle::nonuniformTriangle(const nonuniformTriangle& theTriangle) 
									 : p1(theTriangle.p1), p2(theTriangle.p2), p3(theTriangle.p3)
{
	this->centerx = theTriangle.centerx;
	this->centery = theTriangle.centery;
	this->rediusSQ = theTriangle.rediusSQ;
}

//一般情况下几乎总要遵循operator=输入和返回的都是类对象的引用的原则
nonuniformTriangle& nonuniformTriangle::operator =(const nonuniformTriangle& theTriangle) 						
{
	p1 = theTriangle.p1;
	p2 = theTriangle.p2;
	p3 = theTriangle.p3;

	this->centerx = theTriangle.centerx;
	this->centery = theTriangle.centery;
	this->rediusSQ = theTriangle.rediusSQ;

	return *this;
}

nonuniformTriangle::nonuniformTriangle(const gpoint *inp1,  
									   const gpoint *inp2, 
									   const gpoint *inp3):p1(inp1), p2(inp2), p3(inp3)
{	
	this->computeCircle();
}

void nonuniformTriangle::computeCircle()
{
	float a,b,c,d,e,f;
	a = 2.0f*(this->p1->cx - this->p2->cx);
	b = 2.0f*(this->p1->cy - this->p2->cy);
	c = this->p1->cx*this->p1->cx + this->p1->cy*this->p1->cy - 
		this->p2->cx*this->p2->cx - this->p2->cy*this->p2->cy;

	d = 2.0f*(this->p1->cx - this->p3->cx);
	e = 2.0f*(this->p1->cy - this->p3->cy);
	f = this->p1->cx*this->p1->cx + this->p1->cy*this->p1->cy - 
		this->p3->cx*this->p3->cx - this->p3->cy*this->p3->cy;

	this->centerx = (c*e-b*f) / (a*e-b*d);
	this->centery = (a*f-c*d) / (a*e-b*d);

	this->rediusSQ = (this->p1->cx - this->centerx)*(this->p1->cx - this->centerx) + 
				     (this->p1->cy - this->centery)*(this->p1->cy - this->centery);

	float tmp1 =  (this->p2->cx - this->centerx)*(this->p2->cx - this->centerx) + 
		(this->p2->cy - this->centery)*(this->p2->cy - this->centery);

	float tmp2 =  (this->p3->cx - this->centerx)*(this->p3->cx - this->centerx) + 
		(this->p3->cy - this->centery)*(this->p3->cy - this->centery);


	if(AppGloble::detailPrint)
	cout<<endl<<(long)this<<endl
		<<"<"<<this->p1->cx<<",\t"<<this->p1->cy<<">\t"
		<<"<"<<this->p2->cx<<",\t"<<this->p2->cy<<">\t"
		<<"<"<<this->p3->cx<<",\t"<<this->p3->cy<<">"<<endl
		<<"cx = "<<this->centerx<<"\tcy="<<this->centery<<"\t"
		<<"r="<<sqrt(this->rediusSQ)<<"\t"<<sqrt(tmp1)<<"\t"<<sqrt(tmp2);
		

	a=0.0f;

}

bool nonuniformTriangle::isInCircle(const gpoint &inp)
{
	float disSQ = (inp.cx - this->centerx)*(inp.cx - this->centerx) +
				  (inp.cy - this->centery)*(inp.cy - this->centery);	
	
	return (this->rediusSQ - disSQ > 0.0f);//nonuniformTriangle::inDst);
}

bool nonuniformTriangle::isInCircle(const gpoint *inp)
{
	if(NULL==inp)
		return false;

	float disSQ = (inp->cx - this->centerx)*(inp->cx - this->centerx) +
				  (inp->cy - this->centery)*(inp->cy - this->centery);	

	return (this->rediusSQ - disSQ > 0.0f);//nonuniformTriangle::inDst);
}

//======================================================================

bool trangleFansTerrainGridCreate(unsigned char* dataBlob, const int lenx, const int leny)
{
	cout<<endl<<"in function trangleFansTerrainGridCreate"<<endl;

	if(dataBlob==NULL)
		return false;

	float *theData = (float*)dataBlob;

	AppGloble::terrainCallListNum = glGenLists(1);

	glNewList(AppGloble::terrainCallListNum, GL_COMPILE);

	//glBegin(GL_POINTS);	
	//float tmp=0.0;
	//long count=0;

	float xrate=0.0f;
	float yrate = 0.0f;

	float renderSizex = 3.0;
	float renderSizey = 3.0;
	float btwY = renderSizey/leny;
	float btwX = renderSizex/lenx;
	//int equcount = 0;

	//bool skipping = false;
	float cenval;
	//for(int row=512; row<618; ++row)
	const float maxZ = 12000.0f;
	for(int row=1; row<leny-1; row+=2)
	{
		yrate = float(row)/float(leny);

		for(int col=1; col<lenx-1; col+=2)
		{
			xrate = float(col)/float(lenx);

			cenval = theData[row*lenx+col];

			if(abs(cenval-theData[row*lenx+col-1+lenx])	< 1.0e-6 &&
				abs(cenval-theData[row*lenx+col-1])		< 1.0e-6 &&
				abs(cenval-theData[row*lenx+col-1-lenx])	< 1.0e-6 &&
				abs(cenval-theData[row*lenx+col-lenx])		< 1.0e-6 &&
				abs(cenval-theData[row*lenx+col+1-lenx])	< 1.0e-6 &&
				abs(cenval-theData[row*lenx+col+1])		< 1.0e-6 &&
				abs(cenval-theData[row*lenx+col+1+lenx])	< 1.0e-6 &&
				abs(cenval-theData[row*lenx+col+lenx])		< 1.0e-6)
				continue;

			glBegin(GL_TRIANGLE_FAN);				

			glVertex3f(xrate		*renderSizex,	yrate			*renderSizey, cenval						/maxZ);
			glVertex3f((xrate-btwX)	*renderSizex,	(yrate-btwY)	*renderSizey, theData[row*lenx+col-1+lenx]	/maxZ);				
			glVertex3f((xrate-btwX)	*renderSizex,	(yrate)			*renderSizey, theData[row*lenx+col-1]		/maxZ);
			glVertex3f((xrate-btwX)	*renderSizex,	(yrate+btwY)	*renderSizey, theData[row*lenx+col-1-lenx]	/maxZ);				
			glVertex3f((xrate)		*renderSizex,	(yrate+btwY)	*renderSizey, theData[row*lenx+col-lenx]	/maxZ);
			glVertex3f((xrate+btwX)	*renderSizex,	(yrate+btwY)	*renderSizey, theData[row*lenx+col+1-lenx]	/maxZ);				
			glVertex3f((xrate+btwX)	*renderSizex,	(yrate)			*renderSizey, theData[row*lenx+col+1]		/maxZ);
			glVertex3f((xrate+btwX)	*renderSizex,	(yrate-btwY)	*renderSizey, theData[row*lenx+col+1+lenx]	/maxZ);			
			glVertex3f((xrate)		*renderSizex,	(yrate-btwY)	*renderSizey, theData[row*lenx+col+lenx]	/maxZ);

			glEnd();

			AppGloble::totalTriCount += 8;
		}	
	}

	//glEnd();
	glEndList();	

	return true;
}

//======================================ROAM

std::vector<gpoint > roamTreeNode::points;//所有的节点坐标


void checkToDivid__(unsigned char* dataBlob, 
				  const int lenx, 
				  const int leny,
				  float renderSizex,
				  float renderSizey,
				  float roughDegree,
				  roamTreeNode * curTN)
{
	float* hvdata = (float*)dataBlob;	

	int xc,yc;
	
	//curTN->getpAx();
	
	xc = int(float(lenx)* (curTN->getpAx() /renderSizex));
	xc = xc>=lenx?lenx-1:(xc<0?0:xc);

	yc = int(float(leny)* ( curTN->getpAy()/renderSizey));
	yc = yc>=leny?leny-1:(yc<0?0:yc);

	float hvPA = hvdata[yc*lenx+xc];
	
		

	xc = int(float(lenx)* ( curTN->getpBx()/renderSizex));
	xc = xc>=lenx?lenx-1:(xc<0?0:xc);

	yc = int(float(leny)* ( curTN->getpBy()/renderSizey));
	yc = yc>=leny?leny-1:(yc<0?0:yc);

	float hvPB = hvdata[yc*lenx+xc];
	

	xc = int(float(lenx)* ( curTN->getpCx()/renderSizex));
	xc = xc>=lenx?lenx-1:(xc<0?0:xc);

	yc = int(float(leny)* ( curTN->getpCy()/renderSizey));
	yc = yc>=leny?leny-1:(yc<0?0:yc);

	float hvPC = hvdata[yc*lenx+xc];
	

	//if(abs(hvPA-hvPB)>1.0e-3 || abs(hvPB-hvPC)>1.0e-3 || abs(hvPA-hvPC)>1.0e-3)
	if(abs(hvPA-0.0f)>1.0e-6 || abs(hvPB-0.0f)>1.0e-6 || abs(hvPC-0.0f)>1.0e-6)
	//if(true)
	{
		if(curTN->getDetailLevel()<17)
		{
			curTN->doDivid(RTNDPDOWN);

			checkToDivid__(dataBlob,lenx,leny, 
						 renderSizex, renderSizey, 
						 roughDegree,curTN->getLCNode());

			checkToDivid__(dataBlob,lenx,leny, 
						 renderSizex, renderSizey, 
						 roughDegree,curTN->getRCNode());
		}
		else
		{
			//cout<<endl
			//	<<"ha = "<<hvPA<<"\thb="<<hvPB<<"\thc="<<hvPC
			//	<<"\td="<<curTN->getDetailLevel();
		}
	}
	else
	{
		if(curTN->getDetailLevel()<12)
		{
			//curTN->doDivid(RTNDPDOWN);

			//checkToDivid(dataBlob,lenx,leny, 
			//	renderSizex, renderSizey, 
			//	roughDegree,curTN->getLCNode());

			//checkToDivid(dataBlob,lenx,leny, 
			//	renderSizex, renderSizey, 
			//	roughDegree,curTN->getRCNode());
		}
		else
		{
			cout<<endl
				<<"ha = "<<hvPA<<"\thb="<<hvPB<<"\thc="<<hvPC
				<<"\td="<<curTN->getDetailLevel();
		}
		
	}
}

float*	roamTreeNode::dataBlob = NULL;	
int		roamTreeNode::lenx=1;
int		roamTreeNode::leny=1;
float	roamTreeNode::renderSizex = 1.0f;
float	roamTreeNode::renderSizey = 1.0f;

float gethv(float px, float py)
{
	if(roamTreeNode::dataBlob == NULL)
	{
		return 0.0f;
	}

	try
	{
		int xc = int(float(roamTreeNode::lenx)* (px /roamTreeNode::renderSizex));
		xc = xc>=roamTreeNode::lenx?roamTreeNode::lenx-1:(xc<0?0:xc);

		int yc = int(float(roamTreeNode::leny)* (py /roamTreeNode::renderSizey));
		yc = yc>=roamTreeNode::leny?roamTreeNode::leny-1:(yc<0?0:yc);

		return roamTreeNode::dataBlob[yc*roamTreeNode::lenx+xc];
	}
	catch(...)
	{
		return 0.0f;
	}
}


bool RoamTrianglesCreate(unsigned char* dataBlob, 
						 const int lenx, 
						 const int leny, 
						 const float renderSizex,
						 const float renderSizey,
						 const float roughDegree
						 )
{

	roamTreeNode::dataBlob		= (float*)dataBlob;	
	roamTreeNode::renderSizex	= renderSizex;
	roamTreeNode::renderSizey	= renderSizey;
	roamTreeNode::lenx			= lenx;
	roamTreeNode::leny			= leny;

	roamTreeNode * theluTN = new roamTreeNode(TriAglDrct_UPLEFT,
											  0.0f, 0.0f, 
											  AppGloble::renderSizex);

	roamTreeNode * therdTN = new roamTreeNode(TriAglDrct_DOWNRIGHT,
											  renderSizex, renderSizey, 
											  renderSizex);

	theluTN->linkNodes(therdTN);

	if(false)
	{
		theluTN->doDivid(RTNDPLEFT);
		therdTN->doDivid(RTNDPLEFT);
	}
	else
	{
   
		std::stack<roamTreeNode * > rtnStack;
		rtnStack.push(therdTN);
		rtnStack.push(theluTN);

		roamTreeNode * curTN; 
		//float *hvdata  = (float*)dataBlob;
		float hvPA,hvPB,hvPC;	
		//int xc,yc;

		while(!rtnStack.empty())
		{
			curTN = rtnStack.top();
			rtnStack.pop();

			//xc = int(float(lenx)* (curTN->getpAx() /renderSizex));
			//xc = xc>=lenx?lenx-1:(xc<0?0:xc);
			//yc = int(float(leny)* ( curTN->getpAy()/renderSizey));
			//yc = yc>=leny?leny-1:(yc<0?0:yc);
			hvPA = gethv(curTN->getpAx(), curTN->getpAy());

			//xc = int(float(lenx)* ( curTN->getpBx()/renderSizex));
			//xc = xc>=lenx?lenx-1:(xc<0?0:xc);
			//yc = int(float(leny)* ( curTN->getpBy()/renderSizey));
			//yc = yc>=leny?leny-1:(yc<0?0:yc);
			hvPB = gethv(curTN->getpBx(), curTN->getpBy());//hvdata[yc*lenx+xc];

			//xc = int(float(lenx)* ( curTN->getpCx()/renderSizex));
			//xc = xc>=lenx?lenx-1:(xc<0?0:xc);
			//yc = int(float(leny)* ( curTN->getpCy()/renderSizey));
			//yc = yc>=leny?leny-1:(yc<0?0:yc);
			hvPC = gethv(curTN->getpCx(), curTN->getpCy());//hvdata[yc*lenx+xc];

			if(abs(hvPA-hvPB)>1.0e-3 
			|| abs(hvPB-hvPC)>1.0e-3 
			|| abs(hvPA-hvPC)>1.0e-3)
			//if(abs(hvPA-0.0f)>1.0e-6 || abs(hvPB-0.0f)>1.0e-6 || abs(hvPC-0.0f)>1.0e-6)
			//if(true)
			{
				if(curTN->getDetailLevel()<AppGloble::roamDividDepth)
				{
					curTN->doDivid(RTNDPDOWN);

					rtnStack.push(curTN->getLCNode());
					rtnStack.push(curTN->getRCNode());				
				}
				else
				{
					//cout<<endl
					//	<<"ha = "<<hvPA<<"\thb="<<hvPB<<"\thc="<<hvPC
					//	<<"\td="<<curTN->getDetailLevel();
				}
			}
			else
			{
				cout<<endl
					<<"ha = "<<hvPA<<"\thb="<<hvPB<<"\thc="<<hvPC
					<<"\td="<<curTN->getDetailLevel();
			}
		}
	
		//checkToDivid(dataBlob,lenx,leny,
		//			 renderSizex, renderSizey, 
		//			 roughDegree,therdTN);

		//checkToDivid(dataBlob,lenx,leny,	 
		//			 renderSizex, renderSizey, 
		//			 roughDegree,theluTN);

		//theluTN->doDivid(RTNDPDOWN);
		//theluTN->doDivid(RTNDPLEFT);
		//therdTN->doDivid(RTNDPRIGHT);
		//theluTN->travelChildren();
		//therdTN->travelChildren();	

	}
	std::vector<int> trpcds;

	theluTN->travelChildrenToCreateGrid(trpcds);

	therdTN->travelChildrenToCreateGrid(trpcds);

	AppGloble::terrainCallListNum = glGenLists(1);

	glNewList(AppGloble::terrainCallListNum, GL_COMPILE);

	glBegin(GL_TRIANGLES);				

	gpoint tmpp;
	for(unsigned int k=0; k<trpcds.size();++k)
	{
		tmpp = roamTreeNode::points[trpcds[k]];
		glVertex3f(tmpp.cx, tmpp.cy, tmpp.hv);
	}
	glEnd();

	glEndList();	

	AppGloble::totalTriCount = trpcds.size()/3;

	delete theluTN;
	delete therdTN;

	return true;
}

roamTreeNode::roamTreeNode(TriAglDrct tdrct, 
						   float pointAx, 
						   float pointAy, 
						   float thelenT)
{
	this->detailLevel = 0;

	float thehv = gethv(pointAx, pointAy);

	roamTreeNode::points.push_back(gpoint(pointAx, pointAy,thehv));	
	this->pA = roamTreeNode::points.size()-1;

	this->theDrct = tdrct;
	this->lenT = thelenT;

	gpoint pointB;
	gpoint pointC;

	switch(this->theDrct)
	{
	case TriAglDrct_UP :
		{
			pointB.cx = pointAx - lenT*0.7071f;
			pointB.cy = pointAy + lenT*0.7071f;

			pointC.cx  = pointAx + lenT*0.7071f;
			pointC.cy = pointAy + lenT*0.7071f;

			break;
		}
	case TriAglDrct_UPRIGHT :
		{
			pointB.cx = pointAx - lenT;
			pointB.cy = pointAy;

			pointC.cx = pointAx;
			pointC.cy = pointAy + lenT;

			break;
		}
	case TriAglDrct_RIGHT :
		{
			pointB.cx = pointAx - lenT*0.7071f;
			pointB.cy = pointAy - lenT*0.7071f;

			pointC.cx = pointAx - lenT*0.7071f;
			pointC.cy = pointAy + lenT*0.7071f;

			break;
		}
	case  TriAglDrct_DOWNRIGHT :
		{
			pointB.cx = pointAx;
			pointB.cy = pointAy - lenT;

			pointC.cx = pointAx - lenT;
			pointC.cy = pointAy;

			break;
		}
	case  TriAglDrct_DOWN :
		{
			pointB.cx = pointAx + lenT*0.7071f;
			pointB.cy = pointAy - lenT*0.7071f;

			pointC.cx = pointAx - lenT*0.7071f;
			pointC.cy = pointAy - lenT*0.7071f;

			break;
		}
	case  TriAglDrct_DOWNLEFT :
		{
			pointB.cx = pointAx + lenT;
			pointB.cy = pointAy;

			pointC.cx = pointAx;
			pointC.cy = pointAy - lenT;

			break;
		}
	case  TriAglDrct_LEFT :
		{
			pointB.cx = pointAx + lenT*0.7071f;
			pointB.cy = pointAy + lenT*0.7071f;

			pointC.cx = pointAx + lenT*0.7071f;
			pointC.cy = pointAy - lenT*0.7071f;

			break;
		}
	case  TriAglDrct_UPLEFT :
		{
			pointB.cx = pointAx;
			pointB.cy = pointAy + lenT;

			pointC.cx = pointAx + lenT;
			pointC.cy = pointAy;

			break;
		}
	default:
		{
		}
	}

	pointB.hv = gethv(pointB.cx, pointB.cy);
	pointC.hv = gethv(pointC.cx, pointC.cy);

	roamTreeNode::points.push_back(pointB);	
	this->pB = roamTreeNode::points.size()-1;
    
	roamTreeNode::points.push_back(pointC);	
	this->pC = roamTreeNode::points.size()-1;

	this->parentNode = NULL;	

	this->LeftChild = NULL;		

	this->RightChild = NULL;		

	this->BaseNeighbor = NULL;		

	this->LeftNeighbor = NULL;		

	this->RightNeighbor = NULL;	
}


roamTreeNode::roamTreeNode(roamTreeNode* theParent, bool isLeft, int newPAindex) 
{
	this->parentNode = theParent;
	this->detailLevel = theParent->detailLevel+1;
	this->lenT = theParent->lenT * 0.7071f;

	this->pA = newPAindex;

	if(isLeft)
	{
		this->pB = theParent->pA;
		this->pC = theParent->pB;

		this->theDrct = (TriAglDrct)((theParent->theDrct+3)%8);

		this->BaseNeighbor = theParent->LeftNeighbor;
	}
	else
	{
		this->pB = theParent->pC;
		this->pC = theParent->pA;

		this->theDrct = (TriAglDrct)((theParent->theDrct+5)%8);

		this->BaseNeighbor = theParent->RightNeighbor;
	}

	this->LeftChild = NULL;		

	this->RightChild = NULL;		

	this->LeftNeighbor = NULL;		

	this->RightNeighbor = NULL;	
}

void roamTreeNode::travelChildren()
{	
	cout<<endl;
	for(int p=0; p<this->detailLevel; ++p)
	{
		cout<<"\t";
	}
	//cout<<" PAx="<<this->pAx<<",pAy="<<this->pAy
	//	<<",PBx="<<this->pBx<<",pBy="<<this->pBy
	//	<<",PCx="<<this->pCx<<",pCy="<<this->pCy
	//	<<",drc="<<this->theDrct;

	if(this->LeftChild!=NULL)
		this->LeftChild->travelChildren();
	if(this->RightChild!=NULL)
		this->RightChild->travelChildren();
}

void roamTreeNode::travelChildrenToCreateGrid(std::vector<int>& trpcds)
{
	if(this->LeftChild!=NULL)
	{
		this->LeftChild->travelChildrenToCreateGrid(trpcds);
		this->RightChild->travelChildrenToCreateGrid(trpcds);
	}
	else
	{
		trpcds.push_back(this->pA);
		//trpcds.push_back(roamTreeNode::points[this->pA].cy);
		//trpcds.push_back(roamTreeNode::points[this->pA].hv);

		trpcds.push_back(this->pB);
		//trpcds.push_back(roamTreeNode::points[this->pB].cy);
		//trpcds.push_back(roamTreeNode::points[this->pB].hv);

		trpcds.push_back(this->pC);
		//trpcds.push_back(roamTreeNode::points[this->pC].cy);
		//trpcds.push_back(roamTreeNode::points[this->pC].hv);
	}	
}

bool roamTreeNode::linkNodes(roamTreeNode* anotherNode)
{
	if(this->detailLevel!=0 || anotherNode->detailLevel!=0)
		return false;

	if(anotherNode==NULL)
	{
		if(this->BaseNeighbor!=NULL)
		{
			delete this->BaseNeighbor;
		}		
		this->BaseNeighbor = NULL;		
	}
	else
	{
		this->BaseNeighbor = anotherNode;
		anotherNode->BaseNeighbor = this;

		anotherNode->pB = this->pC;
		anotherNode->pC = this->pB;
	}
	return true;
}

void roamTreeNode::doDividWithBreakPointReady(DividPoint theDPoint,int breakPointIndex)
{
	if(theDPoint==RTNDPLEFT)
	{
		this->doDivid(RTNDPDOWN);
		this->LeftChild->doDividWithBreakPointReady(RTNDPDOWN, breakPointIndex);
	}
	else if(theDPoint==RTNDPRIGHT)
	{
		this->doDivid(RTNDPDOWN);
		this->RightChild->doDividWithBreakPointReady(RTNDPDOWN, breakPointIndex);
	}
	else
	{
		if(this->LeftChild!=NULL || this->RightChild!=NULL)
			return;

		this->LeftChild = new roamTreeNode(this, true, breakPointIndex);
		this->RightChild = new roamTreeNode(this, false, breakPointIndex);

		this->LeftChild->LeftNeighbor = this->RightChild;		
		this->RightChild->RightNeighbor = this->LeftChild;

		if(this->BaseNeighbor!=NULL)
		{
			if(abs(this->BaseNeighbor->theDrct - this->theDrct)==4)
			{
				//this->BaseNeighbor->doDivid(RTNDPDOWN);

				this->RightChild->LeftNeighbor = this->BaseNeighbor->LeftChild;
				this->LeftChild->RightNeighbor = this->BaseNeighbor->RightChild;
			}
			else if(this->BaseNeighbor->theDrct - this->theDrct == -1 || 
				this->BaseNeighbor->theDrct - this->theDrct == 7 )
			{
				this->BaseNeighbor->doDivid(RTNDPRIGHT);

				this->RightChild->LeftNeighbor = this->BaseNeighbor->RightChild->LeftChild;
				this->LeftChild->RightNeighbor = this->BaseNeighbor->RightChild->RightChild;
			}
			else
			{
				this->BaseNeighbor->doDivid(RTNDPLEFT);

				this->RightChild->LeftNeighbor = this->BaseNeighbor->LeftChild->LeftChild;
				this->LeftChild->RightNeighbor = this->BaseNeighbor->LeftChild->RightChild;
			}
		}
	}
}

void roamTreeNode::doDivid(DividPoint theDPoint)
{
	if(theDPoint==RTNDPLEFT)
	{
		this->doDivid(RTNDPDOWN);
		this->LeftChild->doDivid(RTNDPDOWN);
	}
	else if(theDPoint==RTNDPRIGHT)
	{
		this->doDivid(RTNDPDOWN);
		this->RightChild->doDivid(RTNDPDOWN);
	}
	else
	{
		if(this->LeftChild!=NULL || this->RightChild!=NULL)
			return;

		float cnpax;
		float cnpay;

		switch(this->theDrct)
		{
		case TriAglDrct_UP :
			{
				cnpax=roamTreeNode::points[this->pA].cx;
				cnpay=roamTreeNode::points[this->pA].cy + this->lenT*0.7071f;
				break;
			}
		case TriAglDrct_UPRIGHT :
			{				
				cnpax=roamTreeNode::points[this->pA].cx - this->lenT*0.5f;
				cnpay=roamTreeNode::points[this->pA].cy + this->lenT*0.5f;
				break;
			}
		case TriAglDrct_RIGHT :
			{
				cnpax=roamTreeNode::points[this->pA].cx - this->lenT*0.7071f;
				cnpay=roamTreeNode::points[this->pA].cy;
				break;
			}
		case  TriAglDrct_DOWNRIGHT :
			{			
				cnpax=roamTreeNode::points[this->pA].cx - this->lenT*0.5f;
				cnpay=roamTreeNode::points[this->pA].cy - this->lenT*0.5f;
				break;
			}
		case  TriAglDrct_DOWN :
			{			
				cnpax=roamTreeNode::points[this->pA].cx;
				cnpay=roamTreeNode::points[this->pA].cy - this->lenT*0.7071f;
				break;
			}
		case  TriAglDrct_DOWNLEFT :
			{			
				cnpax=roamTreeNode::points[this->pA].cx + this->lenT*0.5f;
				cnpay=roamTreeNode::points[this->pA].cy - this->lenT*0.5f;
				break;
			}
		case  TriAglDrct_LEFT :
			{				
				cnpax=roamTreeNode::points[this->pA].cx + this->lenT*0.7071f;
				cnpay=roamTreeNode::points[this->pA].cy;
				break;
			}
		case  TriAglDrct_UPLEFT :
			{				
				cnpax=roamTreeNode::points[this->pA].cx + this->lenT*0.5f;
				cnpay=roamTreeNode::points[this->pA].cy + this->lenT*0.5f;
				break;
			}
		default:
			{
			}
		}

		roamTreeNode::points.push_back(gpoint(cnpax,cnpay,gethv(cnpax,cnpay)));

		int newpointindex = roamTreeNode::points.size()-1;
		this->LeftChild = new roamTreeNode(this, true, newpointindex);
		this->RightChild = new roamTreeNode(this, false, newpointindex);
		
		this->LeftChild->LeftNeighbor = this->RightChild;		
		this->RightChild->RightNeighbor = this->LeftChild;
		

		if(this->BaseNeighbor!=NULL)
		{
			if(abs(this->BaseNeighbor->theDrct - this->theDrct)==4)
			{
				this->BaseNeighbor->doDividWithBreakPointReady(RTNDPDOWN,newpointindex);

				this->RightChild->LeftNeighbor = this->BaseNeighbor->LeftChild;
				this->LeftChild->RightNeighbor = this->BaseNeighbor->RightChild;
			}
			else if(this->BaseNeighbor->theDrct - this->theDrct == -1 || 
				    this->BaseNeighbor->theDrct - this->theDrct == 7 )
			{
				this->BaseNeighbor->doDividWithBreakPointReady(RTNDPRIGHT,newpointindex);

				this->RightChild->LeftNeighbor = this->BaseNeighbor->RightChild->LeftChild;
				this->LeftChild->RightNeighbor = this->BaseNeighbor->RightChild->RightChild;
			}
			else
			{
				this->BaseNeighbor->doDividWithBreakPointReady(RTNDPLEFT,newpointindex);

				this->RightChild->LeftNeighbor = this->BaseNeighbor->LeftChild->LeftChild;
				this->LeftChild->RightNeighbor = this->BaseNeighbor->LeftChild->RightChild;
			}
		}
	}
}
